package 力扣.堆;

import java.util.*;

public class 前k个高频单词692 {
    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        List<String> strings = topKFrequent(words, k);
        System.out.println(strings);
    }
    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        for (String s: words) {
            hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
        }
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (hashMap.get(o1) == hashMap.get(o2)){//若次数相同则比较单词顺序（字典序）（String的compareTo方法可以比较两个String类型的大小）
                    return o2.compareTo(o1);
                }else {
                    return hashMap.get(o1) - hashMap.get(o2);
                }
            }
        });
        Set<String> keySet = hashMap.keySet();
        Iterator<String> iterator = keySet.iterator();
        while (iterator.hasNext()){
            String word = iterator.next();
            pq.offer(word);
            if (pq.size() > k){
                pq.poll();
            }
        }
        LinkedList<String> ans = new LinkedList<>();
        while (!pq.isEmpty()){
            ans.add(pq.poll());
        }
        Collections.reverse(ans);
        return ans;
    }
}
